package tree.leetcode_617_easy;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null || t2 == null){
            return t1 != null ? t1 : t2;
        }
        //在 t1 上进行合并，对两棵树进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(t1);
        queue.offer(t2);
        while(!queue.isEmpty()){
            TreeNode r1 = queue.poll();
            TreeNode r2 = queue.poll();
            // 修改 t1 为合并后的结果
            r1.val = r1.val + r2.val;
            if(r1.left != null && r2.left != null){
                queue.offer(r1.left);
                queue.offer(r2.left);
            }else if(r1.left == null){
                r1.left = r2.left;
            }
            if(r1.right != null && r2.right != null){
                queue.offer(r1.right);
                queue.offer(r2.right);
            }else if(r1.right == null){
                r1.right = r2.right;
            }
        }
        return t1;
    }
}
